package com.cty._02_HighQualityCode._18_01_DeleteNodeInList;

/**
 * @Auther: cty
 * @Date: 2020/7/5 11:30
 * @Description: 面试题18（一）：在O(1)时间删除链表结点
 * 题目：给定单向链表的头指针和一个结点指针，定义一个函数在O(1)时间删除该节点。
 * @version: 1.0
 */
class LinkedList{
    ListNode first;

    public LinkedList(){
        first = null;
    }

    public void insertFirst(ListNode node){
        node.next = first;
        first = node;
    }

    public void displayList(){
        ListNode current = first;
        while(current != null) {
            System.out.print(current.value + " ");
            current = current.next;
        }
        System.out.println();
    }

    public void deleteNode(ListNode toBeDeleted){
        if(first==null || toBeDeleted==null)
            return;

        if(toBeDeleted.next != null){  // 非尾节点
            toBeDeleted.value = toBeDeleted.next.value;
            toBeDeleted.next = toBeDeleted.next.next;
            return;
        }else if(first == toBeDeleted){  // 尾节点，但只有一个节点
            first = null;
        }else{
            ListNode current = first;
            while(current.next != toBeDeleted)
                current = current.next;
            current.next = null;
        }
    }  // end DeleteNode()
}  // end class

class ListNode{
    int value;
    ListNode next;

    public ListNode() {
    }

    public ListNode(int value) {
        this.value = value;
    }
}  // end class
